home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / plane / _range_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  9.4 KB  |  405 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _range_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/impl/range_tree.h>
  18.  
  19.  
  20. // Let's start with some simple member functions of class rt_elem
  21.  
  22. // the 2-dimensional constructor
  23. //
  24. rt_elem::rt_elem(GenPtr k0, GenPtr k1, GenPtr i) {
  25.   rt_keys=new GenPtr[2];
  26.   rt_keys[0]=k0; rt_keys[1]=k1;
  27.   rt_inf=i;
  28. }
  29.  
  30. // the 3-dimensional constructor
  31. //
  32. rt_elem::rt_elem(GenPtr k0, GenPtr k1, GenPtr k2, GenPtr i) {
  33.   rt_keys=new GenPtr[3];
  34.   rt_keys[0]=k0; rt_keys[1]=k1; rt_keys[2]=k2;
  35.   rt_inf=i;
  36. }
  37.  
  38. // the d-dimensional constructor
  39. //
  40. rt_elem::rt_elem(int dim, GenPtr* k, GenPtr i) {
  41.   rt_keys=new GenPtr[dim];
  42.   for( int d=0; d<dim; d++ )
  43.     rt_keys[d]=k[d];
  44.   rt_inf=i;
  45. }
  46.  
  47.  
  48.  
  49. // And here are the member functions of class range_tree
  50.  
  51. // insert new_elem into the primary tree and update its secondary 
  52. // structures if lev<dim-1
  53. //
  54. void range_tree::rt_insert( rt_item new_elem )
  55. {
  56.  
  57. #ifdef DEBUG
  58.   newline;
  59.   for( int auxl=0; auxl<lev; auxl++ ) cout << "\t";
  60.   cout << "insert " << (int) new_elem->inf() << ":   "; cout.flush();
  61. #endif
  62.  
  63.   if( lev<dim-1 ) {            // take care of secondary structures
  64.  
  65.     base_tree_item p, new_leaf;
  66.     range_tree* sec;
  67.  
  68.     // insert the new element into the primary tree 
  69.     //
  70.     aux.clear();
  71.     new_leaf = base_tree::insert( new_elem, new_range_tree(dim,lev+1), 
  72.                               new_range_tree(dim,lev+1) );
  73.   
  74.     // now we insert the new element into all secondary structures of 
  75.     // nodes on the path from the root to the new leaf with a non-empty
  76.     // secondary structure (remember that these nodes are not in aux)
  77.     //
  78.     p = root();
  79.     while( p ) {
  80.       sec = (range_tree*) inf(p);
  81.       if( sec->size() )
  82.         sec->rt_insert(new_elem);
  83.       if( cmp(new_elem,key(p))<=0 )
  84.         p = l_child(p);
  85.       else
  86.         p = r_child(p);
  87.     }
  88.  
  89.     // and into the (empty) secondary structure of the new leaf
  90.     //
  91.     ((range_tree*) inf(new_leaf))->rt_insert(new_elem);
  92.  
  93.     // for all nodes appended to aux by the function propagate_change(), 
  94.     // we rebuild the secondary structure from scratch
  95.     //
  96.     rt_item* elem_array = new rt_item[size()];        // array of elements
  97.     int elem_no;                    // number of elements
  98.  
  99.     forall( p, aux ) {
  100.       elem_no = elements_in_subtree(elem_array, p);
  101.       ((range_tree*) inf(p))->build_tree(elem_array, 0, elem_no-1);
  102.     }
  103.   
  104.     delete elem_array;
  105.   }
  106.   else
  107.     // for lev==dim-1 the range tree is just an ordinary search tree
  108.     //
  109.     base_tree::insert( new_elem, 0, 0 );
  110. }
  111.  
  112.  
  113.  
  114.  
  115.  
  116. // recursively build a range tree for the elements 
  117. // elem_array[lidx],...,elem_array[ridx]
  118. // if p==0 we build the tree on this level and the secondary structure of the
  119. // root, otherwise we just build the secondary structure of p
  120. //
  121. void range_tree::build_tree( rt_item* elem_array, int lidx, int ridx, 
  122.                  base_tree_item p )
  123. {
  124.  
  125. #ifdef DEBUG
  126.   newline;
  127.   for( int gg=0; gg<lev; gg++ )
  128.     cout << "\t";
  129.   cout << "build_tree " << p << ":   ";
  130.   cout.flush();
  131. #endif
  132.  
  133.   int i;
  134.  
  135.   // the last level of the range tree is just a binary search tree
  136.   //
  137.   if( lev==dim-1 ) {
  138.     for( i=lidx; i<=ridx; i++ ) {
  139.  
  140. #ifdef DEBUG
  141.       newline;
  142.       for( int gg=0; gg<lev; gg++ )
  143.         cout << "\t";
  144.       cout << "insert " << (int) elem_array[i]->inf() << ":   ";
  145.       cout.flush();
  146. #endif
  147.  
  148.       base_tree::insert( elem_array[i], 0, 0 );
  149.     }
  150.     return;
  151.   }
  152.  
  153.   // we are entering this level for the first time, therefor we have
  154.   // to insert all elements and sort them according to the new level
  155.   //
  156.   if( !p ) {
  157.     for( i=lidx; i<=ridx; i++ ) {
  158.  
  159. #ifdef DEBUG
  160.       newline;
  161.       for( int gg=0; gg<lev; gg++ )
  162.         cout << "\t";
  163.       cout << "insert " << (int) elem_array[i]->inf() << ":   ";
  164.       cout.flush();
  165. #endif
  166.  
  167.       base_tree::insert( elem_array[i], new_range_tree(dim,lev+1), 
  168.                                         new_range_tree(dim,lev+1) );
  169.     }
  170.     p = root();
  171.     elem_array = new rt_item[ridx-lidx+1];
  172.     lidx = 0;
  173.     ridx = elements_in_subtree(elem_array,p)-1;    /* get sorted array */
  174.   }
  175.  
  176.   // build the secondary structure
  177.   //
  178.   ((range_tree*) inf(p))->build_tree(elem_array, lidx, ridx);
  179.  
  180.   // if p is an inner node, we recursively build the secondary structures
  181.   // of its children
  182.   //
  183.   if (is_inner(p)) {
  184.     int l=lidx, r=ridx, med=(l+r)/2, c=cmp(elem_array[med],key(p));
  185.  
  186.     // "split" the array at key(p)
  187.     //
  188.     while( c ) {
  189.       if( c>0 )
  190.     r = med-1;
  191.       else
  192.     l = med+1;
  193.       med = (l+r)/2;
  194.       c = cmp(elem_array[med], key(p));
  195.     }
  196.  
  197.     if (r_child(p))
  198.       build_tree(elem_array, med + 1, ridx, r_child(p));
  199.     if (l_child(p))
  200.       build_tree(elem_array, lidx, med, l_child(p));
  201.   }
  202.  
  203.   // free the memory of the array elem_array, if we are done
  204.   //
  205.   if( p==root() )
  206.     delete elem_array;
  207. }
  208.  
  209.  
  210.  
  211. // compute a sorted array (according to the actual level) of all 
  212. // elements in the subtree rooted at subroot and return their number
  213. //
  214. int range_tree::elements_in_subtree( rt_item* elem_array, 
  215.                      base_tree_item subroot )
  216. {
  217.   int elem_no=0;
  218.   base_tree_item p=subroot, q=subroot;
  219.  
  220.   while( is_inner(p) )            // find leftmost leaf
  221.     p = l_child(p);
  222.   while( is_inner(q) )            // find rightmost leaf
  223.     q = r_child(q);
  224.  
  225.   while( p!=q ) {            // collect all elements inbetween
  226.     elem_array[elem_no++] = rt_item(key(p));
  227.     p = succ(p);
  228.   }
  229.   elem_array[elem_no++] = rt_item(key(q));
  230.  
  231.   return elem_no;            // return the number of elements
  232. }
  233.  
  234.  
  235.  
  236.  
  237. // return a list of all elements in the tree whose key is between
  238. // left and right on each level
  239. //
  240. void range_tree::rt_query( rt_item& left, rt_item& right, 
  241.                list<rt_item>& res )
  242. {
  243.   if( size()>0 ) {            // avoid special case
  244.     base_tree_item p, q;
  245.  
  246.     if( lev<dim-1 ) {            // we have to perform recursive quieries
  247.  
  248.       // find the last node common to both search paths
  249.       //
  250.       p = root();
  251.       while( is_inner(p) ) {
  252.     if( cmp(right,key(p))<=0 )
  253.       p = l_child(p);
  254.     else if( cmp(left,key(p))>0 )
  255.       p = r_child(p);
  256.     else
  257.       break;
  258.       }
  259.  
  260.       if( is_inner(p) ) {
  261.  
  262.         // traverse the left subpath
  263.     //
  264.     q = l_child(p);
  265.     while( is_inner(q) ) {
  266.       if( cmp(left,key(q))<=0 ) {
  267.         if( r_child(q) )
  268.           // recursively query all nodes right to the subpath
  269.           //
  270.           ((range_tree*) inf(r_child(q)))->rt_query(left,right,res);
  271.         q = l_child(q);
  272.       }
  273.       else
  274.         q = r_child(q);
  275.     }
  276.     if( cmp(left,key(q))<=0 && cmp(right,key(q))>=0 )
  277.       ((range_tree*) inf(q))->rt_query(left,right,res);
  278.  
  279.         // traverse the right subpath
  280.     //
  281.     q = r_child(p);
  282.     while( is_inner(q) ) {
  283.       if( cmp(right,key(q))>0 ) {
  284.         if( l_child(q) )
  285.           // recursively query all nodes left to the subpath
  286.           //
  287.           ((range_tree*) inf(l_child(q)))->rt_query(left,right,res);
  288.         q = r_child(q);
  289.       }
  290.       else
  291.         q = l_child(q);
  292.     }
  293.     if( cmp(left,key(q))<=0 && cmp(right,key(q))>=0 )
  294.       ((range_tree*) inf(q))->rt_query(left,right,res);
  295.       }
  296.       else {
  297.         // we only have to look at one leaf
  298.     //
  299.     if( cmp(left,key(p))<=0 && cmp(right,key(p))>=0 )
  300.       ((range_tree*) inf(p))->rt_query(left,right,res);
  301.       }
  302.     }
  303.     else {
  304.       // append all elements between left and right on level dim-1
  305.       // to the res
  306.       //
  307.       p = locate_succ( left );
  308.       while( p && cmp(key(p),right)<=0 ) {
  309.         res.append( rt_item(key(p)) );
  310.         p = succ(p);
  311.       }
  312.     }
  313.   }
  314. }
  315.  
  316.  
  317.  
  318. // delete elem in the primary tree and update its secondary 
  319. // structures if lev<dim-1
  320. //
  321. void range_tree::rt_del( rt_item elem )
  322. {
  323.   if( lev<dim-1 ) {            // take care of secondary structures
  324.     base_tree_item p;
  325.  
  326.     // delete elem in all secondary structures on the search path to elem
  327.     //
  328.     p = root();
  329.     while( is_inner(p) ) {
  330.       ((range_tree*) inf(p))->rt_del(elem);
  331.       if( cmp(elem,key(p))<=0 )
  332.         p = l_child(p);
  333.       else
  334.         p = r_child(p);
  335.     };
  336.  
  337.     // and in the primary tree
  338.     //
  339.     aux.clear();
  340.     base_tree::del_item(p);
  341.  
  342.     // for all nodes appended to aux by the function propagate_change(), 
  343.     // we rebuild the secondary structure from scratch
  344.     //
  345.     rt_item* elem_array = new rt_item[size()];        // array of elements
  346.     int elem_no;                    // number of elements
  347.  
  348.     forall( p, aux ) {
  349.       elem_no = elements_in_subtree(elem_array, p);
  350.       ((range_tree*) inf(p))->build_tree(elem_array, 0, elem_no-1);
  351.     }
  352.   
  353.     delete elem_array;
  354.   }
  355.   else
  356.     // for lev==dim-1 the range tree is just an ordinary search tree
  357.     //
  358.     base_tree::del(elem);
  359. }
  360.  
  361.  
  362.  
  363. // return a list of all elements in the tree
  364. //
  365. list<rt_item> range_tree::all_items()
  366. {
  367.   list<rt_item> res;
  368.  
  369.   if( !empty() ) {
  370.     base_tree_item p=base_tree::min(),
  371.                    q=base_tree::max();
  372.     res.append( (rt_item) key(p) );
  373.     while( p!=q ) {
  374.       p = cyclic_succ(p);
  375.       res.append( (rt_item) key(p) );
  376.     }
  377.   }
  378.   return res;
  379. }
  380.  
  381.  
  382.  
  383. // compute minimum element on a given level
  384. //
  385. rt_item range_tree::rt_min( int d ) 
  386. {
  387.   if( empty() ) return 0;
  388.   if( lev<d )                    // proceed to next level
  389.     return ((range_tree*) inf(root()))->rt_min(d);
  390.   else 
  391.     return( (rt_item) key(base_tree::min()) );
  392. }
  393.  
  394.  
  395.  
  396. // compute maximum element on a given level
  397. //
  398. rt_item range_tree::rt_max( int d ) {
  399.   if( empty() ) return 0;
  400.   if( lev<d )                    // proceed to next level
  401.     return ((range_tree*) inf(root()))->rt_max(d);
  402.   else 
  403.     return( (rt_item) key(base_tree::max()) );
  404. }
  405.